1. Field of the Invention
This present invention relates generally to computer operating systems and in particular, the implementation of a system and method for reducing the amount of free physical space that needs to be reserved in a system which incorporates a compressed main memory.
2. Discussion of the Prior Art
FIG. 1(a) depicts one example of a block diagram of a computing system 100 incorporating a compressed memory management capability. The computing system 100 includes, for example, one or more processors 102, operating system 125, a cache 104, a compression controller 106, compressed main memory 108 and one or more input/output (“I/O”) devices 110, each of which is described in detail below.
As is known, processor(s) 102 are the controlling center of the computing system 100. The processor(s) 102 execute at least one operating system (“OS”) (125) which controls the execution of programs and processing of data. Examples include, but are not limited to, an OS such as that sold under the trademark AIX by International Business Machines (“IBM”) Corporation and an OS sold under the trademark WINDOWS NT by the Microsoft Corporation. As will be described below, the operating system 125 is one component of the computing environment 100 that can incorporate and use the capabilities of the present invention.
Coupled to the processor(s) 102 and the compression controller 106 (described below), is a cache memory 104. The cache memory 104 provides a short term, high-speed, high-capacity computer memory for data retrieved by the compression controller 106 from the I/O devices 110 and/or the compressed main memory 108.
Coupled to the cache 104 and the compressed memory 108 is the compression controller 106, (described in detail below) which manages, for example, the transfer of information between the I/O devices 110 and the cache 104, and/or the transfer of information between the compressed main memory 108 and the cache 104. Functions of the compression controller include the compression/decompression of data; and the storing of the resulting compressed lines in blocks of fixed size. This preferably includes a mapping from real page addresses, as seen by the operating system, to addresses of fixed-size blocks in memory 108.
The compressed main memory 108, which is also coupled to the compression controller 106, contains data which is compressed, for example, in units of cache lines. In one embodiment, each page includes four cache lines. Cache lines are decompressed and compressed respectively when inserted or cast-out of cache 104. Pages from I/O devices 110 are also compressed (in units of cache liens) on insertion into main memory 108. In this example, I/O is done into and out of the cache 104. Although a single cache is shown, for simplicity, an actual system may include a hierarchy of caches.
As is well known, information relating to pages of memory can be stored in one or more page tables in the main memory or the cache 104 and is used by the OS 125. One example of a page table 140 is depicted in FIG. 1(b). Page table 140 includes a plurality of page table entries 142 and each entry includes, for instance, a virtual address 144 for a given page; a real address 146 corresponding to the virtual address for that page; and a set of management information 148 for the page, for example, a use bit field indicating whether the page has been referenced and a read/write or read-only access field indicating the allowed type of access.
The real address of a page is mapped into a set of physical addresses (e.g., identifiers of blocks of storage) for each cache line, when the page is requested from main memory 108. In one example, this is accomplished using tables 150 and 160, illustrated in FIG. 1(c). These tables can be stored in the compression controller 106. Table 150 includes, for instance, what is termed the real page address for a page, Page (i), as well as a list of the memory blocks for each line of the page. For example, each page could be 4 k bytes in size and includes four cache lines. Each cache line is 1 k bytes in size.
Compressed cache lines are stored in fixed-size blocks of 256 bytes, as one example. Table 160 includes, for instance, the compressed blocks making up a particular line of Page (i). For example, line 1 of Page (i) includes three compressed blocks, each having 256 bytes. Since, in this example, each page can include up to four cache lines and each cache line can include up to four compressed blocks of memory, each page may occupy up to 16 blocks of memory.
Referring again to the system depicted in FIG. 1(a), the compression controller 106 may include one or more interrupt registers 120 and a free-space list 112. One implementation of the free-space list is as a linked list, which is well known to those of skill in the art.
Here, the compression controller 106 performs various functions, including:                a) compressing lines which are cast out of the cache 104, and storing the results in some number of fixed-size blocks drawn from the free-space list 112;        b) decompressing lines on cache fetches;        c) blocks freed by operations such as removing a line from memory, or compressing a changed line which now uses less space, are added to the free-space list 112;        d) maintaining a count F of the number of blocks on the free-space list 112. This count is preferably available to the OS 125 on request; and        e) maintaining a set of thresholds implemented as interrupt registers (120) on the size of F. Changes in F that cause thresholds to be crossed cause a processor interrupt. Preferably, each threshold can be dynamically set by software and at least those related to measured quantities are stored in an interrupt register 120 in the controller 106.        
As further shown in FIG. 1(a), the free-space manager 130 maintains an appropriate number of blocks on the free-space list 112. Too few such blocks causes the system to abend or suspend execution of applications pending page-outs, while having too many such blocks is wasteful of storage, producing excessive page faults. The free-space manager also sets the interrupt registers 120 with one or more thresholds (T0 . . . TN) at which interrupts are generated. Threshold values which are related to actual measured values, as opposed to periodically measured values, are stored in one or more interrupt registers 120. Examples of thresholding policies and control processes are described in detail in commonly-owned, co-pending U.S. Patent Application No. 09/021,338 (YO997-338), entitled COMPRESSION STORE FREE-SPACE MANAGEMENT, the whole contents and disclosure of which are incorporated herein by reference. Further shown in FIG. 1(a) is the presence of Reclaim list 134 having pages which represent page frames that may be used immediately upon request by the operating system since a valid copy of every page on the reclaim list exists on disk.
A solution to the requirement for additional space when performing pageouts is to maintain sufficient amounts of free physical space. However, this can be quite wasteful of physical storage, since the required pageouts may involve substantial traversals of large objects such as page tables, whose worst case expansion needs to be accounted for. This is considered memory in a used but available state.
For instance, with respect to the computer system 100 implementing a shared cache memory as illustrated in FIG. 1(a), the controller device 106 is configured to maintain a count “F” having a value representing the amount of free space available to the computer operating system. Generally, F must be sufficient to permit pageouts to be performed which amount of space is denoted as a number F*. If F decreases below a threshold T1, where T1>=F*, the memory controller issues an interrupt to the processor. This interrupt stops normal processing and initiates the recovery of free space by deleting or paging out to disk a sufficient number of pages to increase the amount of free space available to above a second threshold T2. Generally the reserve represented by T1 can be quite large, representing a substantial amount of unused and thus wasted space.
It would thus be highly desirable to provide a system and method for reducing the amount of reserve space required for performing pageouts to disk.
It would further be highly desirable to provide a system and method for reducing the amount of reserve space required for performing pageouts by keeping much of the reserve in a set of pages which can be deleted by the interrupt handler, but which may also be referenced and used by the system.
It would additionally be highly desirable to provide a system and method for reducing the amount of reserve space required for performing pageouts to disk and enabling pageouts to be performed without the need for a general traversal of page tables and paging I/O.